package a10_动态规划;

import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * a26_单词拆分复习3
 * </p>
 *
 * @author flyduck
 * @since 2025/4/18
 */
public class a26_单词拆分复习3 {
    public static void main(String[] args) {
        a26_单词拆分复习3 test = new a26_单词拆分复习3();
        System.out.println(test.wordBreak("catsandog", Arrays.asList("cats", "dog", "sand", "and", "cat")));
    }
    //dp[i]：表示长度为i的字符串能否拆分成功
    //递推公式：
    //dp[j] == true
    //j ~ i-1如果在wordDict里面就可以
    public boolean wordBreak(String s, List<String> wordDict) {
        char[] chars = s.toCharArray();

        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if(dp[j] && wordDict.contains(splitArray(chars,j, i-1))){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }

    private String splitArray(char[] chars,int leftIdx,int rightIdx){
        StringBuilder sb = new StringBuilder();
        while (leftIdx <= rightIdx){
            sb.append(chars[leftIdx]);
            leftIdx++;
        }
        return sb.toString();
    }
}
